import java.util.ArrayList;

/**
 * An implementation of the classic insertion sort, with runtime {@code &theta
 * (lgn)}
 */
public class InsertionSort
{
    public static ArrayList<Integer> sortInts(ArrayList<Integer> list)
    {
        int i, j, key, count = 0;

        for (j = 1; j < list.size(); j++) {
            key = list.get(j);
            i = j - 1;
            while (i >= 0 && key < list.get(i)) {
                list.set(i + 1, list.get(i));
                i -= 1;
                count++;
            }
            list.set(i + 1, key);
            count++;
        }
        System.out.println("Iterations: " + count);

        return list;
    }

    public static int[] sortInts(int[] list)
    {
        int i, j, key, count = 0;

        for (j = 1; j < list.length; j++) {
            key = list[j];
            i = j - 1;
            while (i >= 0 && key < list[i]) {
                list[i + 1] = list[i];
                i -= 1;
                count++;
            }
            list[i + 1] = key;
            count++;
        }
        System.out.println("Iterations: " + count);

        return list;
    }

}
